package LeetCode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Num496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> st=new ArrayDeque<>();
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = nums2.length-1; i >=0 ; i--) {//单调栈一般都倒序遍历，保证要找的元素都被处理过了
            //例如[2,5,3,6,8,4,7,1],要找6右侧第一个比他大的数字，答案是8，由于是倒序遍历得来答案，
            //所以一定保证了8是和后面的所有元素做过比较的，他就是第一个比6大的元素
            while (!st.isEmpty() && nums2[i]>st.peek()){
                st.pop();
            }
            map.put(nums2[i],st.isEmpty()?-1:st.peek());
            st.push(nums2[i]);
        }
        for (int i = 0; i < nums1.length ; i++) {
            nums1[i]=map.get(nums1[i]);
        }
        return nums1;
    }
}
